The present invention relates to data processing systems and more particularly to queue structures which may be utilized in such systems.
Queue structures are used primarily for the management of data structures, without the necessity for moving bulk information around in data processing systems, by use of a pointer or header. The queue is used to schedule tasks which are performed on a priority basis. This is done dynamically during processing. Processing is conducted within a task being performed rather than scheduling such processing. Queues are also used in communication buffers for queuing calls. The structures of the present invention may be managed on a last-in, first-out (LIFO) or on a first-in, first-out (FIFO) basis. Queues may also be utilized to maintain a list of free working memory ordered by size or by address. The order of removal of the queues is independent of the order of insertion. In the prior art, it has been known to utilize what has been called an associative memory in order to accommodate the queuing structures. This associative memory technique although theoretically appealing is in actual practice unsuited to handle such queuing tasks due to the relatively high cost and slow access time. In the prior art, as taught in the U.S. Pat. No. 3,449,722, issued June 10, 1969, a new and improved queuing scheme for multiprocessing systems was described in which program requests which cannot be immediately operated on are temporarily stored so that upon the freeing of an originally busy processor section, the oldest queued program request for the particular processor section would be accommodated. Such United States patent suggested the use of a common queue for each such section in the system which could be separately accessed, thereby, by use of the common queue, having established a capability of a string of requests relative to each of the processor sections comprising the data processing system, and thereby avoiding undue expenditure for hardware which is required by such queues. In such queuing structures in data processing systems it is, however, important to provide such queuing structure in a manner such that the queue or frames which are inserted in a list of such queues or frames may be accessed, i.e., enqueued or dequeued, in any manner dependent or independent of the priority of the tasks or subtasks identified by such queues.
It is accordingly a primary object of the present invention to provide an improved queue structure for use in a data processing system by which the queue structure may be accessed for enqueuing or dequeuing based on the priority of the frames in such queue structure or independent of the priority of such frames, or based on the address of such frames.